package com.hy;

import java.util.Stack;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:二叉树的迭代遍历
 * author: Mr.Du
 * Date: 2023/9/5
 * Time: 9:29
 */
public class IterateThrough {

    public static void inOrderTraversal(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        if(root != null) stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            if(node != null){
                if(node.right != null) stack.push(node.right);
                if(node.left != null) stack.push(node.left);
                stack.push(node);
                stack.push(null);
            }else{
                node = stack.pop();
                System.out.print(node.val + " ");
            }
        }
    }

    public static void preOrderTraversal(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        if(root != null) stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            if(node != null){
                if(node.right != null) stack.push(node.right);
                stack.push(node);
                stack.push(null);
                if(node.left != null) stack.push(node.left);
            }else{
                node = stack.pop();
                System.out.print(node.val + " ");
            }
        }
    }

    public static void postOrderTraversal(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        if(root != null) stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            if(node != null){
                stack.push(node);
                stack.push(null);
                if(node.right != null) stack.push(node.right);
                if(node.left != null) stack.push(node.left);
            }else{
                node = stack.pop();
                System.out.print(node.val + " ");
            }
        }
    }


    public static void main(String[] args) {
        // Create a sample binary tree
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        System.out.print("In-order traversal: ");
        inOrderTraversal(root);
        System.out.println();
        System.out.print("Pre-order traversal: ");
        preOrderTraversal(root);
        System.out.println();
        System.out.print("Post-order traversal: ");
        postOrderTraversal(root);
    }
}
